package 力扣;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author yyq
 * @create 2022-04-19 9:45
 */
public class leetcode235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p==root) return p;
        if(q==root) return q;
        // son parent
        HashMap<TreeNode,TreeNode> map = new HashMap<>();
        Set<TreeNode> set =new HashSet<>();
        preOrder(map,root,root);
        TreeNode parent = map.get(p);
        set.add(p);
        set.add(parent);
        while (map.containsKey(parent)){
            parent = map.get(parent);
            set.add(parent);
        }
        parent = q;
        while (!set.contains(parent)){
            parent = map.get(parent);
        }
        return parent;
    }

    private void preOrder(HashMap<TreeNode, TreeNode> map, TreeNode parent, TreeNode root) {
        if(parent!=root){
            map.put(root,parent);
        }
        if(root.left!=null){
            preOrder(map,root,root.left);
        }
        if(root.right!=null){
            preOrder(map,root,root.right);
        }
    }
}
